import java.util.*;

public class TextDemo {
    public static void countintSort9(int[] array){
        int[] count = new int[9];
        HashMap<Integer,Queue<Integer>> map = new HashMap<>();
        for(int element:array){
            if(!map.containsKey(element-1)){
                map.put(element-1,new LinkedList<>());
            }
            count[element-1]++;
            map.get(element-1).add(element);
        }
        int index = 0;
        for(int i = 0;i<9;i++){
            while(count[i]!=0){
                array[index++] = map.get(i).remove();
                count[i]--;
            }
        }
    }
   public static void countintSort09(int[] array){
       int[] count = new int[9];
       for(int element:array){
           count[element-1]++;
       }
       int index = 0;
       for(int i = 0;i<array.length;i++){
           while(count[i]!=0){
               array[index++] = i+1;
               count[i]--;
           }
       }
   }
    public static int reversePairs(int[] nums) {
        if (nums.length == 0) return 0;
        int[] result = new int[nums.length];
        return mergeSortAndCount(nums, 0, nums.length - 1, result);
    }
    // 对 arr 的 [start, end] 区间归并排序
    private static int mergeSortAndCount(int[] arr, int start, int end, int[] result) {
        // 只剩下一个数字，停止拆分
        if (start == end) return 0;
        int middle = (start + end) / 2;
        // 拆分左边区域，并将归并排序的结果保存到 result 的 [start, middle] 区间，记录左边逆序对数量
        int leftCount = mergeSortAndCount(arr, start, middle, result);
        // 拆分右边区域，并将归并排序的结果保存到 result 的 [middle + 1, end] 区间，记录右边逆序对数量
        int rightCount = mergeSortAndCount(arr, middle + 1, end, result);
        // 合并左右区域到 result 的 [start, end] 区间，记录合并过程中的逆序对数量
        int crossCount = mergeAndCount(arr, start, end, result);
        // 三者之和就是 [start, end] 区间内产生的所有逆序对数量
        return leftCount + rightCount + crossCount;
    }
    // 将 result 的 [start, middle] 和 [middle + 1, end] 区间合并，并记录逆序对数量
    private static int mergeAndCount(int[] arr, int start, int end, int[] result) {
        int count = 0;
        int end1 = (start + end) / 2;
        int start2 = end1 + 1;
        // 用来遍历数组的指针
        int index1 = start;
        int index2 = start2;
        while (index1 <= end1 && index2 <= end) {
            if (arr[index1] <= arr[index2]) {
                result[index1 + index2 - start2] = arr[index1++];
            } else {
                result[index1 + index2 - start2] = arr[index2++];
                // 当右边数字较小时，统计左边剩余数字的数量，也就是此数字可与左边数组组成的逆序对数量
                count += end1 - index1 + 1;
            }
        }
        // 将剩余数字补到结果数组之后
        while (index1 <= end1) {
            result[index1 + index2 - start2] = arr[index1++];
        }
        while (index2 <= end) {
            result[index1 + index2 - start2] = arr[index2++];
        }
        // 将 result 操作区间的数字拷贝到 arr 数组中，以便下次比较
        while (start <= end) {
            arr[start] = result[start++];
        }
        return count;
    }
    private static int mergeAndCount(int[] array,int left,int mid,int right,int[] tem){
        for(int i = left;i<=right;i++){
            tem[i] = array[i];
        }
        int i = left;
        int j =mid+1;
        int count = 0;
        for(int k = left;k<=right;k++){
            if(i==mid+1){
                array[k] = tem[j];
                j++;
            }else if(j==right+1){
                array[k] = tem[i];
                i++;
            }else if(tem[i]<=tem[j]){
                array[k] = tem[j];
                i++;
            }else{
                array[k] = tem[j];
                j++;
                count+=(mid-i+1);
            }
        }
        return count;
    }
    public static void mergeSort(int[] array){
        int[] result = new int[array.length];
        mergeSort(array,0,array.length-1,result);
    }
    private static void mergeSort(int[] array,int start,int end,int[] result){
        if(start==end) return;
        int middle = (start+end)/2;
        mergeSort(array,start,middle,result);
        mergeSort(array,middle+1,end,result);
        merge(array,start,end,result);
    }
    private static void merge(int[] array,int start,int end,int[] result){
        int middle = (start+end)/2;
        int index1 = start;
        int index2 = middle+1;
        while(index1<=middle && index2<=end){
            if(array[index1]<=array[index2]){
                result[index1+index2-middle-1] = array[index1++];
            }else{
                result[index1+index2-middle-1] = array[index2++];
            }
        }
        while(index1<=middle){
            result[index1+index2-middle-1] = array[index1++];
        }
        while(index2<=end){
            result[index1+index2-middle-1] = array[index2++];
        }
        while(start<=end){
            array[start] = result[start++];
        }
    }
    public static void main(String[] args) {
        int[] array = new int[]{2,7,5,9,3,5,7,8,1};
        countintSort9(array);
        System.out.println(Arrays.toString(array));
    }
    public static int[] mergeSortNor(int[] array){
        return mergeSortNor(array,0,array.length-1);
    }
    private static int[] mergeSortNor(int[] array,int start,int end){
        if(start==end){
            return new int[]{array[start]};
        }
        int middle = (start+end)/2;
        int[] left = mergeSortNor(array,start,middle);
        int[] right = mergeSortNor(array,middle+1,end);

        return mergeNor(left,right);
    }
    private static int[] mergeNor(int[] array1,int[] array2){
        int[] result = new int[array1.length+array2.length];
        int index1 = 0;
        int index2 = 0;
        while(index1<array1.length && index2<array2.length){
            if(array1[index1]<=array2[index2]){
                result[index1+index2] = array1[index1++];
            }else{
                result[index1+index2] = array2[index2++];
            }
        }
        while(index1<array1.length){
            result[index1+index2] = array1[index1++];
        }
        while(index2<array2.length){
            result[index1+index2] = array2[index2++];
        }
        return result;
    }
    public static void heapSort(int[] array){
        buildHeap(array);
        for(int i = array.length-1;i>0;i--){
            swap(array,0,i);
            maxHeapify(array,0,i);
        }
    }
    private static void buildHeap(int[] array){
        for(int i = array.length/2-1;i>=0;i--){
            maxHeapify(array,i,array.length);
        }
    }
    private static void maxHeapify(int[] array,int i ,int heapSize){
        int left = 2*i+1;
        int right = left+1;
        int last = i;
        if(left<heapSize && array[left]>array[last]){
            last = left;
        }
        if(right<heapSize && array[right]>array[last]){
            last = right;
        }
        if(last!=i){
            swap(array,last,i);
            maxHeapify(array,last,heapSize);
        }
    }
    public static void shellSortNor(int[] array){
        for(int gap = array.length/2;gap>0;gap/=2){
            for(int groupStartIndex = 0;groupStartIndex<gap;groupStartIndex++){
                for(int currentIndex = groupStartIndex+gap;currentIndex<array.length;currentIndex+=gap){
                    int prevIndex = currentIndex-gap;
                    int currentNumber = array[currentIndex];
                    while(prevIndex>=0 && array[prevIndex]>currentNumber){
                        array[prevIndex+gap] = array[prevIndex];
                        prevIndex-=gap;
                    }
                    array[prevIndex+gap] = currentNumber;
                }
            }
        }
    }
    public static void shellSort(int[] array){
        for(int gap = array.length/2;gap>0;gap/=2){
            for(int i = gap;i<array.length;i++){
                int prevIndex = i-gap;
                int currentNumber = array[i];
                while(prevIndex>=0 && array[prevIndex]>currentNumber){
                    array[prevIndex+gap] = array[prevIndex];
                    prevIndex-=gap;
                }
                array[prevIndex+gap] = currentNumber;
            }
        }
    }
    public static void selectionSort(int[] array){
        int minIndex = 0;
        int maxIndex = 0;
        for(int i = 0;i<array.length/2;i++){
            minIndex = i;
            maxIndex = i;
            for(int j = i+1;j<array.length-i;j++){
                if(array[minIndex]>array[j]){
                    minIndex = j;
                }
                if(array[maxIndex]<array[j]){
                    maxIndex = j;
                }
            }
            if(minIndex==maxIndex) return ;
            swap(array,i,minIndex);
            if(maxIndex==i) maxIndex = minIndex;
            int lastIndex = array.length-i-1;
            swap(array,lastIndex,maxIndex);
        }
    }
    public static void insertSort(int[] array){
        for(int i = 1;i<array.length;i++){
            int j = i-1;
            int currentNumber = array[i];
            while(j>=0 && currentNumber<array[j]){
                array[j+1] = array[j];
                j--;
            }
            array[j+1] = currentNumber;
        }
    }
    public static void bubbleSort(int[] array){
        int lastIndex = array.length;
        int swapIndex = 0;
        boolean flag = true;
        while(flag){
            flag = false;
            for(int i = 1;i<lastIndex;i++){
                if(array[i-1]>array[i]){
                    swap(array,i-1,i);
                    flag = true;
                    swapIndex = i;
                }
            }
            lastIndex = swapIndex;
        }
    }
    public static void quickSort(int[] array){
        quickSort(array,0,array.length-1);
    }
    private static void getindexOfThreeIndex(int[] array,int left,int right){
        int minddle = (left+right)/2;
        int index = 0;
       if(array[left]<array[right]){
           if(array[minddle]<array[left]){
               index = left;
           }else if(array[minddle]>array[right]){
               index = right;
           }else{
               index = minddle;
           }
       }else{
           if(array[minddle]<array[right]){
               index = right;
           }else if(array[minddle]>array[left]){
               index = left;
           }else{
               index = minddle;
           }
       }
       swap(array,left,index);
    }
    private static void quickSort(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        //三数区中法；
        getindexOfThreeIndex(array,left,right);

        int pivot = partition(array,left,right);
        quickSort(array,left,pivot-1);
        quickSort(array,pivot+1,right);
    }
    private static int partitionDouble(int[] array,int start,int end){
        int left = start+1;
        int right = end;
        int pivot = array[start];
        while(left<right){
            while(left<right && array[left]<=pivot){
                left++;
            }
            while(left<right && array[right]>=pivot){
                right--;
            }
            if(left<right){
                swap(array,left++,right--);
            }
        }
        if(left==right && array[right]>pivot){
            right--;
        }
        swap(array,start,right);
        return right;
    }
    private static int partition(int[] array,int start,int end){
        int left = start+1;
        int right = end;
        int pivot = array[start];
        while(left<right){
            while(left<right && array[left]<=pivot){
                left++;
            }
            if(left!=right){
                swap(array,left,right);
                right--;
            }
        }
        if(left==right && array[right]>pivot){
            right--;
        }
        if(start!=right){
            swap(array,start,right);
        }
        return right;
    }
    private static void swap(int[] array,int x,int y){
        int tem = array[x];
        array[x] = array[y];
        array[y] = tem;
    }


}
